#include <logbase.h>
#include <genrand.h>
#include <pthread.h>
#include <rbtree_option.h>

// c没有把这些基本数据结构写入标准库中。可能是因为c++有了。
// 二叉树。左小右大规则。但是可能出现线性树。
// 前序遍历，中序遍历，后序遍历。

// 平衡二叉树。每个节点到叶节点深度不超过1.

// 完全二叉树。每一层要依次排满。但实现难。

// 红黑树：
// 性质1. 结点是红色或黑色。 [3]
// 性质2. 根结点是黑色。 [3]
// 性质3. 所有叶子都是黑色。（叶子是NIL结点） [3]
// 性质4. 每个红色结点的两个子结点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色结点）
// 性质5. 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。 [3]

#define rbtreeCheckSize 15
void rbTraversalCallbackInt(struct rbtreeNodeStct *rbUsrNode)
{
    logdebugc("key=%d,val=%d", rbUsrNode->keyval.key32, *rbtreeGetValPtr(rbUsrNode, int32_t));
}

struct rbCheckStruct
{
    int chkVal;
    char chkstr[32];
};
void rbTraversalCallbackStct(struct rbtreeNodeStct *rbUsrNode)
{
    logdebugc("key=%s,val=%d,%s", rbUsrNode->keyval.keystr, rbtreeGetValPtr(rbUsrNode, struct rbCheckStruct)->chkVal,
             rbtreeGetValPtr(rbUsrNode, struct rbCheckStruct)->chkstr);
}

int main(int argc, char **argv)
{
    struct rbtreeNodeStct *tmpusrnode;
    struct rbtreeKeyStct tmpkeys;
    srand(time(NULL));
    if (1)
    {
        struct rbtreeMgrStct tmpRbMgrInt;
        int tmpflag;
        rbtreeMgrInit(&tmpRbMgrInt, rbtreeKeyType_32);
        for (uint64_t i = 0; i < rbtreeCheckSize; i++)
        {
            tmpusrnode = rbtreeMallocOneNode(rbtreeKeyType_32, sizeof(uint32_t));
            tmpusrnode->keyval.key32 = i; // rand() % rbtreeCheckSize;
            *rbtreeGetValPtr(tmpusrnode, uint32_t) = tmpusrnode->keyval.key32;
            rbtreeMgrInsertNode(&tmpRbMgrInt, tmpusrnode);
        }
        // 用户数据为数字， 不用分配空间， 不用释放
        tmpusrnode = rbtreeMallocOneNode(rbtreeKeyType_32, sizeof(uint32_t));
        tmpusrnode->keyval.key32 = 5;
        *rbtreeGetValPtr(tmpusrnode, uint32_t) = 65466;
        rbtreeMgrReplaceNode(&tmpRbMgrInt, tmpusrnode);

        rbtreeMgrTraversal(&tmpRbMgrInt, rbTraversalCallbackInt, 1);
        tmpflag = rbtreeMgrFreeAll(&tmpRbMgrInt);
        logdebugc("free managor, flag=%d", tmpflag);
        rbtreeMgrTraversal(&tmpRbMgrInt, rbTraversalCallbackInt, 1);
        tmpflag = rbtreeMgrFreeAll(&tmpRbMgrInt);
        logdebugc("free managor, flag=%d", tmpflag);
    }
    if (1)
    {
        struct rbtreeMgrStct tmpRbMgrStct;
        rbtreeMgrInit(&tmpRbMgrStct, rbtreeKeyType_Str);
        // check insert.
        for (uint64_t i = 0; i < rbtreeCheckSize; i++)
        {
            tmpusrnode = rbtreeMallocOneNode(rbtreeKeyType_Str, sizeof(struct rbCheckStruct));
            snprintf(tmpusrnode->keyval.keystr, sizeof(tmpusrnode->keyval.keystr), "lx-%d", (int)i);
            memcpy(rbtreeGetValPtr(tmpusrnode, struct rbCheckStruct)->chkstr, tmpusrnode->keyval.keystr, sizeof(tmpusrnode->keyval.keystr));
            rbtreeGetValPtr(tmpusrnode, struct rbCheckStruct)->chkVal = i;
            rbtreeMgrInsertNode(&tmpRbMgrStct, tmpusrnode);
        }
        rbtreeMgrTraversal(&tmpRbMgrStct, rbTraversalCallbackStct, 1);

        strncpy(tmpkeys.keystr, "lx-9", sizeof(tmpkeys.keystr));
        tmpkeys.keytype = rbtreeKeyType_Str;
        tmpusrnode = rbtreeMgrFindNode(&tmpRbMgrStct, &tmpkeys);
        if (tmpusrnode)
        {
            logdebugc("find node = %d,%s", rbtreeGetValPtr(tmpusrnode, struct rbCheckStruct)->chkVal,
                     rbtreeGetValPtr(tmpusrnode, struct rbCheckStruct)->chkstr);
        }

        tmpusrnode = rbtreeMallocOneNode(rbtreeKeyType_Str, sizeof(struct rbCheckStruct));
        snprintf(tmpusrnode->keyval.keystr, sizeof(tmpusrnode->keyval.keystr), "lx-%d", 7);
        memcpy(rbtreeGetValPtr(tmpusrnode, struct rbCheckStruct)->chkstr, tmpusrnode->keyval.keystr, sizeof(tmpusrnode->keyval.keystr));
        rbtreeGetValPtr(tmpusrnode, struct rbCheckStruct)->chkVal = 7784;
        rbtreeMgrReplaceNode(&tmpRbMgrStct, tmpusrnode);
        rbtreeMgrTraversal(&tmpRbMgrStct, rbTraversalCallbackStct, 1);

        strncpy(tmpkeys.keystr, "lx-3", sizeof(tmpkeys.keystr));
        tmpkeys.keytype = rbtreeKeyType_Str;
        rbtreeMgrEraseByKey(&tmpRbMgrStct, &tmpkeys);
        rbtreeMgrTraversal(&tmpRbMgrStct, rbTraversalCallbackStct, 1);

        rbtreeMgrFreeAll(&tmpRbMgrStct);

        rbtreeMgrTraversal(&tmpRbMgrStct, rbTraversalCallbackStct, 1);
    }
    return 0;
}
